N-th digit

Time: O(LogN); Space: O(1); easy

Find the Nth digit of the infinite integer sequence 1,2,3,4,5,6,7,8,9,10,11,…

Note:

  • N is positive and will fit within the range of a 32-bit signed integer (N < 2^31).

Example 1:

Input: n = 3

Output: 3

Example 2:

Input: n = 11

Output: 0

Explanation:

  • The 11th digit of the sequence 1,2,3,4,5,6,7,8,9,10,11, … is a 0, which is part of the number 10.

[1]:

class Solution1(object):
    def findNthDigit(self, N):
        """
        :type N: int
        :rtype: int
        """
        digit_len = 1
        while N > digit_len * 9 * (10 ** (digit_len - 1)):
            N -= digit_len * 9 * (10 ** (digit_len - 1))
            digit_len += 1

        num = 10 ** (digit_len-1) + (N-1)/digit_len

        nth_digit = num // (10 ** ((digit_len-1) - ((N-1) % digit_len)))
        nth_digit %= 10

        return nth_digit

[2]:

s = Solution1()
n = 3
assert s.findNthDigit(n) == 3
n = 11
assert s.findNthDigit(n) == 0